package oop.ex4.search;

import java.util.Deque;
import java.util.LinkedList;
import java.util.concurrent.Callable;

import oop.ex4.crosswords.CrosswordEntry;
import oop.ex4.search.MyDepthFirstSearch.LastIterator;

/**
 * An implementation of a Depth Limited Search for SearchBoards that only
 * looks for the best solutions
 *   
 * @author yomach
 * @author mbattat
 * 
 * @param <B> The search board.
 * @param <M> The search moves.
 */
public class MyBestDepthSearch<B extends SearchBoard<M>, M extends SearchMove> implements Callable<B> {
	
	private B _board;
	
	private int _maxDepth;
	
	///////////////////////////////////////////////////////
	//////////////////////Constructors/////////////////////
	///////////////////////////////////////////////////////
	
	public MyBestDepthSearch(B board, int maxDepth) {
		_board = board;
		_maxDepth = maxDepth;
	}
	
	///////////////////////////////////////////////////////
	/////////////////////Public Method/////////////////////
	///////////////////////////////////////////////////////
	
	@Override
	public B call() throws Exception {
		if (_board.getQualityBound() < 0) { return null; }
		int bestScore = _board.getQualityBound();
		Deque<LastIterator<M>> iteratorStack = new LinkedList<LastIterator<M>>();
		LastIterator<M> iterator = new LastIterator<M>(_board.getMoveIterator());
		boolean keepSearching = true;
		while (keepSearching) {
			if (!iterator.hasNext() || _maxDepth == 0) { // Depth limit or no more moves.
				if (iteratorStack.isEmpty()) { 
					break;
				} // No more moves at all.
				_maxDepth++;
				iterator = iteratorStack.pop();
				_board.undoMove(iterator.last());
				continue;
			}
			M move = iterator.next();
			if (((CrosswordEntry) move).getTerm().equals("dosage")) {
				System.out.println(move);
			}
			_board.doMove(move);
			if (_board.getQualityBound() < bestScore) { // This branch cannot reach top quality.
				_board.undoMove(iterator.last());
				continue;
			}
			if (_board.isBestSolution()) { // This branch hits the jackpot.
				return _board;
			}
			_maxDepth--;
			iteratorStack.push(iterator);
			iterator = new LastIterator<M>(_board.getMoveIterator());
		}
		return null;
	}
}